package lq354;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		int k=sc.nextInt();
		long[][] arr=new long[2001][2001];
		for(int i=1;i<2001;i++) {
			arr[i][1]=1;
			arr[i][i]=1;
		}
		for(int i=2;i<2001;i++) {
			for(int j=2;j<i;j++) {
				arr[i][j]=(arr[i-1][j-1]+arr[i-1][j])%k;
			}
		}
		long[][] res=new long[2001][2001];
		for(int i=1;i<2001;i++) {
			for(int j=1;j<2001;j++) {
				res[i][j]=res[i-1][j]+res[i][j-1]-res[i-1][j-1];
				if (j<=i&&arr[i][j]==0) {
					res[i][j]++;
				}
			}
		}
		while(t>0) {
			int n=sc.nextInt();
			int m=sc.nextInt();
			m=Math.min(n, m);
			System.out.println(res[n+1][m+1]);
			t--;
		}
	}
}
